package com.zy.recursion;

import java.util.LinkedList;
import java.util.List;

/**
 * @description: 第K个语法符号
 * @author: zhaoyi
 * @create: 2019-09-15 13:19
 * https://leetcode-cn.com/explore/orignial/card/recursion-i/260/conclusion/1231/
 **/

public class Kth {


    /**
     * 官方给出的解法 几下位运算懵逼
     * 第 K 位的父位应该是第 (K+1) / 2 位。如果父位是 0，那么这一位就是 1 - (K%2)。如果父位是 1，那么这一位就是 K%2
     * https://leetcode-cn.com/explore/orignial/card/recursion-i/260/conclusion/1232/
     *
     * @param N
     * @param K
     * @return
     */
    public int kthGrammar2(int N, int K) {
        if (N == 1) return 0;
        return (~K & 1) ^ kthGrammar2(N - 1, (K + 1) / 2);
    }


    /**
     * 位运算懵逼，换成正常好理解的方式
     *
     * @param N
     * @param K
     * @return
     */
    public int kthGrammar3(int N, int K) {
        return recursion(N, K - 1);
    }

    public int recursion(int N, int k) {
        if (N == 1) return 0;
        //首先要得到前N - 1排的那个数字
        int num = recursion(N - 1, k / 2);
        if (k % 2 == 0) {
            if (num == 1) {
                return 1;
            } else {
                return 0;
            }
        } else {
            if (num == 1) {
                return 0;
            } else {
                return 1;
            }
        }
    }


    /**
     * 在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。
     * 给定行数 N 和序数 K，返回第 N 行中第 K个字符。（K从1开始）
     * 解释:
     * 第一行: 0
     * 第二行: 01
     * 第三行: 0110
     * 第四行: 01101001
     * 我这有BUG 当N够大就OOM了 java.lang.OutOfMemoryError: Java heap space
     *
     * @param N
     * @param K
     * @return
     */
    public int kthGrammar(int N, int K) {
        List<Integer> ls = found(N);
        ls.forEach(System.out::print);
        System.out.println();
        return ls.get(K - 1);
    }

    private List<Integer> found(int n) {
        List<Integer> ls = new LinkedList<>();
        if (n == 1) {
            ls.add(0);
            return ls;
        } else if (n == 2) {
            ls.add(0);
            ls.add(1);
            return ls;
        } else {
            List<Integer> found = found(n - 1);
            List<Integer> g = gound(found, n);
            ls.addAll(found);
            ls.addAll(g);
            return ls;
        }
    }

    private List<Integer> gound(List<Integer> priveList, int n) {
        List<Integer> ls = new LinkedList();
        if (n % 2 == 0) {
            //取中间镜像
            ls.addAll(new LinkedList<Integer>(priveList.subList(priveList.size() / 2, priveList.size())));
            //List<Integer> ls = new ArrayList<Integer>(priveList.subList(priveList.size() / 2, priveList.size()));
            ls.addAll(priveList.subList(0, priveList.size() / 2));
            return ls;
        } else {
            //不能用 Collections.reverse(priveList);
            //List<Integer> ls = new ArrayList<Integer>((int) Math.pow(2, n - 2));
            for (int i = priveList.size() - 1; i >= 0; i--) {
                ls.add(priveList.get(i));
            }
            return ls;
        }
    }

}
